package com.剑指offer.no38;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Vector;


// 交换法 回溯算法
/*
 * 交换法 —— 回溯算法
 *
 * [a, [b, c]]
 * [b, [a, c]] [c, [b, a]]
 *
 * 如上，对字符串"abc"分割，每次固定一个字符为一部分，
 * 其他字符为另一部分，再将固定字符与其他字符进行交换，
 * 依次遍历每个字符，再进行回溯递归。
 * */

public class Solution {
    ArrayList<String> res = new ArrayList<>();
    char[] c;

    public String[] permutation(String s) {
        if (s.length() < 1) {
            return new String[]{};
        }

        c = s.toCharArray();
        backtrack(0);

        return res.toArray(new String[res.size()]);
    }

    // n为当前递归的层度
    private void backtrack(int n) {
        if (n == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }

        HashSet<Character> set = new HashSet<>();
        for (int i = n; i < c.length; i++) {


            if (set.contains(c[i]))
                // 重复了， 剪枝
                continue;

            set.add(c[i]);

            // 交换，将 c[i] 固定在第 x 位
            swap(i, n);

            // 开启固定第 x + 1 位字符
            backtrack(n + 1);

            // 恢复交换
            swap(i, n);

        }

    }

    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

}


/*
 * 回溯法
 *
 * 字符串的排列和数字的排列都属于回溯的经典问题
 *
 * 回溯算法框架：解决一个问题，实际上就是一个决策树的遍历过程：
 * 1. 路径：做出的选择
 * 2. 选择列表：当前可以做的选择
 * 3. 结束条件：到达决策树底层，无法再做选择的条件
 *
 * 伪代码：
 * result = []
 * def backtrack(路径，选择列表):
 *     if 满足结束条件：
 *         result.add(路径)
 *         return
 *     for 选择 in 选择列表:
 *         做选择
 *         backtrack(路径，选择列表)
 *         撤销选择
 *
 * 核心是for循环中的递归，在递归调用之前“做选择”，
 * 在递归调用之后“撤销选择”。
 *
 * 字符串的排列可以抽象为一棵决策树：
 *                       [ ]
 *          [a]          [b]         [c]
 *      [ab]   [ac]  [bc]   [ba]  [ca]  [cb]
 *     [abc]  [acb] [bca]  [bac]  [cab] [cba]
 *
 * 考虑字符重复情况：
 *                       [ ]
 *          [a]          [a]         [c]
 *      [aa]   [ac]  [ac]   [aa]  [ca]  [ca]
 *     [aac]  [aca] [aca]  [aac]  [caa] [caa]
 *
 * 字符串在做排列时，等于从a字符开始，对决策树进行遍历，
 * "a"就是路径，"b""c"是"a"的选择列表，"ab"和"ac"就是做出的选择，
 * “结束条件”是遍历到树的底层，此处为选择列表为空。
 *
 * 本题定义backtrack函数像一个指针，在树上遍历，
 * 同时维护每个点的属性，每当走到树的底层，其“路径”就是一个全排列。
 * 当字符出现重复，且重复位置不一定时，需要先对字符串进行排序，
 * 再对字符串进行“去重”处理，之后按照回溯框架即可。
 * */
//class Solution02 {
//    ArrayList<String> res = new ArrayList<>();
//    char[] c;
//
//    public String[] permutation(String s) {
//        if (s.length() < 1) {
//            return new String[]{};
//        }
//
//        // 对字符串进行排序
//        //        std::sort(s.begin(), s.end());
//        //        std::vector<std::string> res;
//
//        Vector<>
//        String track = "";
//
//        backtrack(res, s, track, visited);
//
//        return res.toArray(new String[res.size()]);
//    }
//
//    private void backtrack(int n){
//        // 回溯停止的条件
//
//    }
//}